package org.nowcoder.leetcode.DP;

import java.util.Arrays;

/**
 * Title  : 416. Partition Equal Subset Sum
 * Source : https://leetcode.cn/problems/partition-equal-subset-sum/description/
 * Author : XrazYang
 * Date   : 2023-1-16
 */

public class LeetCode_416 {
    public boolean canPartition(int[] nums) {
//        int sum = Arrays.stream(nums).sum();
//
//        //特殊情况
//        if (sum % 2 != 0) {
//            return false;
//        }
//
//        int n = nums.length;
//        int m = sum / 2;
//        int[][] dp = new int[n][m + 1];
//
//        for (int i = nums[0]; i <= m; i++) {
//            dp[0][i] = nums[0];
//        }
//        for (int i = 1; i < n; i++) {
//            for (int j = 1; j <= m; j++) {
//                if (j < nums[i]) {
//                    dp[i][j] = dp[i - 1][j];
//                } else {
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
//                }
//            }
//        }
//        return dp[n - 1][m] == m;

        //滚动数组：空间优化，二维数组降为一维
        int sum = Arrays.stream(nums).sum();
        //特殊情况
        if (sum % 2 != 0) {
            return false;
        }
        int n = nums.length;
        int m = sum / 2;
        int[] dp = new int[m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[m] == m;
    }
}
